/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhong
 *
 */
public class RaceCar {
	Map<String, Double> memo = new HashMap<>();

	public int racecar(int target) {
		int res = 0;
		memo.put("0_1", 0.0);// 初始状态
		res = (int) (Math.min(help(target, -1), help(target, 1)) - 1);
		return res;
	}

	private double help(int target, int speed) {
		String strRep = target + "_" + speed;
		if (!memo.containsKey(strRep)) {
			memo.put(strRep, -1.0);
		} else if (memo.get(strRep) == -1) {// 正在计算又来计算
			return Integer.MAX_VALUE;
		}
		System.out.println("开始计算" + strRep);
		if (memo.get(strRep) == -1) {
			if (Math.abs(speed) > 1) {
				double step = help(target - speed / 2, speed / 2) + 1;
				memo.put(strRep, step);
			} else {
				int max = 0, min = 0;
				if (speed > 0) {// 当前速度为正，则之前为负
					min = -target;
					max = -2;
				} else {
					min = 2;
					max = target;
				}
				double minRes = Integer.MAX_VALUE;
				for (int i = min; i < max; i++) {
					double tmp = help(target, i);
					if (tmp < minRes) {
						tmp = minRes;
					}
				}
				memo.put(strRep, minRes + 1);
			}
		}
		System.out.println(strRep + ":" + memo.get(strRep));
		return memo.get(strRep);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int target = 3;
		System.out.println(new RaceCar().racecar(target));
	}

}
